﻿#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<algorithm>	//算法
using namespace std;


//stl简介和源码文件（见笔记和D:\code\Bit）

//管理字符串的类 - string类（相当于一个字符数组的顺序表）

//严格来说，属于标准库，而非STL

//学stl的技巧：看名字猜功能

//c - str系列库函数管理字符串（比较、长度、拷贝...效率低、效果较差）
//cpp - string类管理字符数组（比较、长度、拷贝... + 增删查改 + 算法）

//基本用法
//int main()
//{
//	string s1;						//创建对象
//	std::string s2;					//创建对象
//	std::string name("zhangsan");	//创建对象并初始化
//	name = "zhangfei";				//赋值
//}
//
//相关成员函数
//int main()
//{
//	//构造
//	string s1;				//无参默认构造，为空
//	string s2("hello world");	//传常量字符串初始化
//	string s3(10, '*');		//用多个字符去初始化。初始化为10个*
//	string s4(s2);			//用已有的对象通过拷贝构造初始化
//	cout << s1 << endl;
//	cout << s2 << endl;
//	cout << s3 << endl;
//	cout << s4 << endl;
//	
//	//从源字符串第n个下标开始拷贝m个字符至目标字符串
//	string s5(s3, 6, 5);	//将s3中的world拷贝给s5
//	string s6(s3, 6);		//若没有指定长度，则默认长度为size_t -1（int类型中的最大值）
//	string s7(s3, 6, 100);	//若指定长度大于源字符串长度，则取较小值（源字符串长度）为要拷贝长度
//	cout << s5 << endl;
//	cout << s6 << endl;
//	cout << s7 << endl;
//
//	//分割字符串
//	string url("https://cplusplus.com/reference/string/string/string/");
//	string sub1(url, 0, 5);
//	string sub2(url, 8, 13);
//	string sub3(url, 22);
//	//string sub3(url, 22, url.size()-22);
//	cout << sub1 << endl;
//	cout << sub2 << endl;
//	cout << sub3 << endl;
//
//	//运算符 "=" 重载
//	s1 = '2';
//	cout << s1 << endl;
//	s1 = "1111";
//	cout << s1 << endl;
//	s1 = s2;
//	cout << s1 << endl;
//
//	//可以直接通过ascll码值比较字符串大小
//	cout << (s1 == s2) << endl;	
//	cout << (s1 > s2) << endl;
//}
// 
// 
//增删查改
//int main()
//{
//	//增
//	string s1("hello");
//	//尾插一个字符
//	s1.push_back(' ');
//	//尾插一个字符串
//	s1.append("world");
//	cout << s1 << endl;
//	//以上成员函数可以自动扩容
//	s1 = "hello";
//	s1 += ' ';		//重载的 += 会调用push_back
//	s1 += "world";  //重载的 += 会调用append
//	cout << s1 << endl;
//
//}
//
//int main()
//{
//	//改
//	int x = 0;
//	cin >> x;
//	//将x转成string对象
//	string xstr;
//	while (x)
//	{
//		size_t val = x % 10;
//		xstr += ('0' + val);
//		x /= 10;
//	}
//	//逆置
//	//...
//}

//5.22

//int main()
//{
//	string s1("hello world");//数组大小为12（包含“\0”）
//	//遍历string
//	//直接流插入
//	cout << s1 << endl;
//	//下标+[]（此处[]是一个重载的运算符）
//	cout << s1.size() << endl;	//11。因为size()不计数“\0”
//	for (size_t i = 0 ; i < s1.size(); i++)
//	{
//		cout << s1[i] << " ";	
//	}
//	cout << endl;
//}

//迭代器（功能类似指针。它可能是指针，也可能不是指针）
//任何容器都支持迭代器，且用法类似
//iterator提供了一种统一的方式访问和修改容器的数据
//int main()
//{
//	//读
//	string s1("hello world");
//	string::iterator it = s1.begin();	//begin()指向的是第一个字符的位置
//	while (it != s1.end())				//end()指向的是最后一个字符的下一个位置
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//	//[补] 范围for遍历读取（底层为迭代器）
//	for (auto ch : s1)
//	{
//		cout << ch << " ";
//	}
//	cout << endl;
//
//	//写
//	it = s1.begin();
//	while (it != s1.end())				
//	{
//		(*it)--;	//it对应的数据可被修改
//		++it;
//	}
//	cout << endl;
//	//[补] 范围for遍历改写（底层为迭代器）	
//	for (auto& ch : s1)
//	{
//		ch++;
//	}
//	cout << endl;
//
//	//迭代器跟容器进行配合
//	reverse(s1.begin(), s1.end());	//逆置算法
//	for (auto ch : s1)
//	{
//		cout << ch << " ";
//	}
//	cout << endl;
//	//容器中的数据是私有的，无法直接访问
//	//而通过迭代器，算法就可以取处理容器中的数据了
//
//}
//
//反向迭代器 reverse_iterator
//int main()
//{
//	string s1("hello world");
//	//string::reverse_iterator rit = s1.rbegin();	//rbegin()指向字符数组最后一个字符的位置
//	auto rit = s1.rbegin();
//	while (rit != s1.rend())	//反向遍历。ps：范围for只能正向遍历，只有反向迭代器存在反向遍历的说法				//rend()指向第一个字符的前一个位置
//	{
//		(*rit) += 3;
//		cout << *rit << " ";
//		++rit;
//	}
//	cout << endl;
//	cout << s1 << endl;
//}
//
//以下代码无法编译通过
//void Func(const string& s)
//{
//	string::iterator it = s.begin();
//	while (it != s.end())
//	{
//
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//}
//int main()
//{
//	string s1("hello world");
//	Func(s1);
//}
//因为const对象不能用普通迭代器，必须用const迭代器（const_iterator / const_reverse_iterator）
//（涉及权限放大）
//修改：
//void Func(const string& s)
//{
//	string::const_iterator it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	string::const_reverse_iterator rit = s.rbegin();
//	//auto rit = s.rbegin();
//	while (rit != s.rend())
//	{
//		cout << *rit << " ";
//		++rit;
//	}
//}
//int main()
//{
//	string s1("hello world");
//	Func(s1);
//}
//普通迭代器可以读可以写，const迭代器只能读不能写

//容量相关
//
//int main()
//{
//	string s1("hello world");
//	cout << s1.size() << endl;
//	//cout << s1.length() << endl;
//	//size() - 数据个数
//	//length() - 其实也是数据个数
//	//length()是在string类被写入标准库时出现的，而size()是STL出现后加入的。
//	//这其实是为了跟其他容器的数据作区分，因为不是所有数据都像字符串有“长度”一说
//
//	//cout << s1.max_size() << endl;	
//	cout << s1.capacity() << endl;
//	//max_size() - 求字符串所能涉及的最大长度
//	//但不同环境下，max_size()所求最大长度不一定相同
//	//capacity() - 求容量。不同环境下，所求容量也不一定相同
//	//capacity()可以进行扩容：
//	size_t old = s1.capacity();
//	for (size_t i = 0; i < 100; i++)
//	{
//		s1 += 'x';
//
//		if (old != s1.capacity())
//		{
//			cout << "扩容：" << s1.capacity() << endl;
//			old = s1.capacity();
//		}
//	}
//	//不同环境下，扩容的结果也不一定相同
//
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//	s1.clear();
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//	//s1.clear() - 清空数据。
//	//只清空数据，但不会将扩容还原
//
//	return 0;
//}

//题目：字符串相加
//给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
//你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
//（解题过程见课程02：40，信息太多总结不出来流程= =）
////版本1
//class Solution {
//public:
//    string addStrings(string num1, string num2) 
//    {
//        int end1 = num1.size() - 1; //取尾
//        int end2 = num2.size() - 1; //取尾
//        int carry = 0;              //取进位
//        string strRet;              //存结果
//        while (end1 >= 0 || end2 >= 0)
//        {
//            int val1 = end1 >= 0 ? num1[end1]-'0' : 0;   //取值
//            int val2 = end2 >= 0 ? num2[end2]-'0' : 0;   //取值
//            int ret = val1 + val2 + carry;
//            carry = ret / 10; ret = ret % 10;   //取进位
//            strRet += ('0' + ret);
//            --end1; --end2;     //往前移一位
//        }
//        if (carry == 1)
//        {
//            strRet += '1';
//        }
//        reverse(strRet.begin(), strRet.end());  //逆置
//
//        return strRet;
//    }
//};
////插入n个数据 o（N）
////
////版本2
//class Solution {
//public:
//    string addStrings(string num1, string num2)
//    {
//        int end1 = num1.size() - 1; 
//        int end2 = num2.size() - 1;
//        int carry = 0;             
//        string strRet;              
//        while (end1 >= 0 || end2 >= 0)
//        {
//            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;   //取值
//            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;   //取值
//            int ret = val1 + val2 + carry;
//            carry = ret / 10; ret = ret % 10;   
//            
//            strRet.insert(strRet.begin(), '0' + ret);  //头插（但以这种方式，效率会降低）
//
//            --end1; --end2;     
//        }
//        if (carry == 1)
//        {
//            strRet.insert(strRet.begin(), '1');
//        }
//
//        return strRet;
//    }
//};
////插入n个数据 o（N^2）
////故尽量使用尾插，而非头插

//5.29

//reserve() - 提前开好一段空间，一般用于扩容，且一般不会缩容。
// 如果所需空间实际比reserve()参数大，reserve()就会开更大的空间
// 故所开空间一定是大于等于参数的
// *但不同平台下（甚至不同版本）的一些特殊情景，可能会发生缩容
//
// void TestPushBackReserve()
//{
//	string s;
//	s.reserve(100);
//	size_t sz = s.capacity();
//	cout << "capacity changed: " << sz << '\n';
//
//
//	cout << "making s grow:\n";
//	for (int i = 0; i < 100; ++i)
//	{
//		s.push_back('c');
//		if (sz != s.capacity())
//		{
//			sz = s.capacity();
//			cout << "capacity changed: " << sz << '\n';
//		}
//	}
//
//	s.clear();
//	cout << "capacity changed: " << sz << '\n';
//
//	s.reserve(10);		//clear()清空后，容量100 -> 10。但vs2019下并不会缩容
//	sz = s.capacity();
//	cout << "capacity changed: " << sz << '\n';
//}
//int main()
//{
//	TestPushBackReserve();
//	return 0;
//}
//
//
//resize() - 开空间+初始化
// 如果resize()参数大于字符串的长度，就会先对空间进行扩容，再进行赋值
// 如果resize()参数小于字符串的长度，会将由参数限定大小的空间之后的数据全部删除，但不会缩容
//
//int main()
//{
//	string s1("hello world");
//
//	s1.reserve(100);
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//	//reserve()只开空间，单纯地扩容，不会对所开空间作任何处理
//
//	//s1.resize(200);
//	s1.resize(200, 'x');
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//	// resize()不仅会开空间，还可以赋值来初始化
//
//	s1.resize(20);
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//
//	s1.resize(0);
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//
//	return 0;
//}
//
//
//operator[]
//
// 
//at
//
//int main()
//{
//	try {
//		string s1("hello world");
//		s1.at(0) = 'x';
//		cout << s1 << endl;
//		//s1[15];  // 暴力处理(断言）
//		s1.at(15); // 温和的错误处理（抛出异常）
//	}
//	catch (const exception& e)
//	{
//		cout << e.what() << endl;
//	}
//
//	return 0;
//}
//
//
//operator +=
//
//
//append - 尾插/追加
//assign - 全覆盖后赋值
//insert - 插入（效率低）
//int main()
//{
//	string s1("hello world");
//	s1.append("ssssss");
//	cout << s1 << endl;
//
//	s1.assign("111111111");
//	cout << s1 << endl;
//
//	s1.insert(0, "hello");	//头插
//	cout << s1 << endl;
//		
//	s1.insert(5, "world");	//中间插入
//	cout << s1 << endl;
//
//	s1.insert(0, 10, 'x');	//指定位置处按指定长度插入
//	cout << s1 << endl;
//
//	s1.insert(s1.begin()+10, 10, 'y');	//指定位置处按指定长度插入
//	cout << s1 << endl;
//
//	return 0;
//}
//
// 
//erase - 删除（效率低）
// 
//int main()
//{
//	string s1("hello world");
//	s1.erase(5, 1);			//从指定位置删除指定长度
//	cout << s1 << endl;
//
//	s1.erase(5);			//从尾向前删除指定长度
//	cout << s1 << endl;
//
//	string s2("hello world");
//	s2.erase(0, 1);			//从头删除指定长度
//	cout << s2 << endl;
//
//	s2.erase(s2.begin());	//从尾向前删除指定长度
//	cout << s2 << endl;
//
//	return 0;
//}
//
//
//replace - 替换（效率低）
//c_str() - 返回底层字符数组为字符串
//int main()
//{
//	// world替换成 xxxxxxxxxxxxxxxxxxxxxx
//	string s1("hello world hello bit");
//	s1.replace(6, 5, "xxxxxxxxxxxxxxxxxxxxxx");	//从指定位置开始，将指定长度替换成新字符串
//	cout << s1 << endl;
//
//	//eg：所有空格替换成20%
//	//可以用replace，但效率太低
//	string s2("hello world hello bit");
//	string s3;
//	for (auto ch : s2)
//	{
//		if (ch != ' ')
//		{
//			s3 += ch;
//		}
//		else
//		{
//			s3 += "20%";
//		}
//	}
//	s2 = s3;
//	//cout << s2 << endl;
//	cout << s2.c_str() << endl;
//
//	//c_str()与c的一些接口函数配合
//	string filename = "test.cpp";
//	filename += ".zip";
//
//	FILE* fout = fopen(filename.c_str(), "r");
//
//	return 0;
//}
//
//
//find - 查找字符/字符串
//返回第一个匹配到的字符的位置，没有找到返回string::npos
//substr - 从指定区间截取字符串
//int main()
//{
//	string url = "https://legacy.cplusplus.com/reference/string/string/";
//	//网址 = 协议 + 域名 + 资源名
//
//	//找协议
//	size_t pos1 = url.find("://");
//	string protocol;
//	if (pos1 != string::npos)	//判断是否找到
//	{
//		protocol = url.substr(0, pos1);	//找到则赋值
//	}
//	cout << protocol << endl;
//
//	//找域名和资源名
//	string domain;	//域名
//	string uri;		//资源名
//	size_t pos2 = url.find('/', pos1 + 3);	//从 pos1 + 3 处开始找 '/'
//	if (pos2 != string::npos)
//	{
//		domain = url.substr(pos1 + 3, pos2 - (pos1 + 3));
//		uri = url.substr(pos2 + 1);
//	}
//	cout << domain << endl;
//	cout << uri << endl;
//
//	return 0;
//}
// 
// 
// find_first_of
// 
//int main()
//{
//	std::string str("Please, replace the vowels in this sentence by asterisks.");
//	std::size_t found = str.find_first_of("abc");
//	while (found != std::string::npos)
//	{
//		str[found] = '*';
//		found = str.find_first_of("abc", found + 1);
//	}
//
//	std::cout << str << '\n';
//
//	return 0;
//}

//题目：字符串最后一个单词的长度
//计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。
//int main()
//{
//	string str;
//	//cin >> str;	//流提取读取数据以第一次" "为结束标志
//	getline(cin, str);	//故使用getline()
//	size_t pos = str.rfind(" ");	//从后往前找第一个" "
//	if (pos != string::npos)
//	{
//		cout << str.size() - (pos + 1) << endl;
//	}
//	else
//	{
//		cout << str.size() << endl;
//	}
//
//	return 0;
//}

//
//to_string - int转字符串
//stoi - char转字符串
//stod - 字符串转double
//int main()
//{
//	string stri = to_string(1234);
//	string strd = to_string(11.22);
//	return 0;
//}
// 
//[拓展]编码 ascll和unicode（见笔记）
//int main()
//{
//	char str1[] = "abcd";
//	char str2[2];
//	str2[0] = 98;
//
//	cout << str2[0] << endl;
//
//	char str3[] = "比特";
//	cout << sizeof(str3) << endl;
//	cout << str3 << endl;
//
//
//	str3[1]--;
//	cout << sizeof(str3) << endl;
//	cout << str3 << endl;
//
//	return 0;
//}